package leetcode.editor.cn.q1_300.q;

import java.util.Arrays;

/**
 * @author qidi
 * @date 2021-11-09 14:13:18
 */
class Q0031_NextPermutation {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void nextPermutation(int[] nums) {
            if (nums.length == 1) return;

            int index = -1;
            int max = 0;
            for (int i = nums.length - 1; i >= 0; i--) {
                if (max > nums[i]) {
                    index = i;
                    break;
                }
                if (max < nums[i]) {
                    max = nums[i];
                }
            }
            if (index != -1) {
                // 找到最接近 index && 比 index 大的值
                int i = index + 1;
                int minIndex = index + 1;
                for (; i < nums.length; i++) {
                    if (nums[index] < nums[i] && nums[minIndex] >= nums[i]) {
                        minIndex = i;
                    }
                }
                int tmp = nums[index];
                nums[index] = nums[minIndex];
                nums[minIndex] = tmp;
            }

            Arrays.sort(nums, index + 1, nums.length);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0031_NextPermutation().new Solution();
        int[] arr = {3, 2, 1};
        solution.nextPermutation(arr);
        System.out.println(Arrays.toString(arr));
        solution.nextPermutation(arr);
        System.out.println(Arrays.toString(arr));
        solution.nextPermutation(arr);
        System.out.println(Arrays.toString(arr));
        solution.nextPermutation(arr);
        System.out.println(Arrays.toString(arr));
        solution.nextPermutation(arr);
        System.out.println(Arrays.toString(arr));
        solution.nextPermutation(arr);
        System.out.println(Arrays.toString(arr));
        solution.nextPermutation(arr);
        System.out.println(Arrays.toString(arr));
        solution.nextPermutation(arr);
        System.out.println(Arrays.toString(arr));
        solution.nextPermutation(arr);
        System.out.println(Arrays.toString(arr));
        solution.nextPermutation(arr);
        System.out.println(Arrays.toString(arr));
    }
}